--[[
    直接插入排序
    假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。
    按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。
    可做优化的点的
        1. 时间复杂度O(n^2)
        2. 性能上优于冒泡排序，选择排序

    node = {
        id 作为大小比较值
    }
--]]


require("dump")

local table_insert = table.insert
local table_remove = table.remove

local ISort = {}

function ISort.new(...)
    local instance = setmetatable({}, {__index=ISort})
    instance:ctor(...)
    return instance
end

function ISort:ctor()
    self.nodes = {} --用于存放数据
end

--
function ISort:push(node)
    table_insert(self.nodes, node)
    return
end

--优先取id值大的node
function ISort:pop()
    if not self.nodes or not self.nodes[1] then
        return
    end
    local value = self.nodes[1]
    table_remove(self.nodes, 1)
    return value
end

function ISort:getTop()
    return self.nodes[1]
end

function ISort:getNodes()
    return self.nodes
end

function ISort:print()
    for i = 1, #self.nodes do
        print(i, self.nodes[i].id)
    end
end

function ISort:size()
    return #self.nodes
end

function ISort:sort()
    local len = self:size()
    for i=1, len do
        for j=i, 2, -1 do
            if self.nodes[j].id < self.nodes[j-1].id  then
                --小的在左边
                local tmp = self.nodes[j]
                self.nodes[j] = self.nodes[j-1]
                self.nodes[j-1] = tmp
            else
                break
            end
        end
    end
end

------------------------------------------------------------------
--测试
------------------------------------------------------------------
if arg and arg[0] == "isort.lua" then
    local isort = ISort.new()
    isort:push({id=2})
    isort:push({id=12})
    isort:push({id=1})
    isort:push({id=8})
    isort:push({id=6})
    isort:push({id=5})
    isort:push({id=6})
    isort:push({id=16})
    isort:push({id=26})
    isort:print()
    print("_______")
    isort:sort()
    isort:print()
    print("_______")

    print("____min:", tostring(isort:pop()))
    --print("____min:", tostring(ISort:pop()))
end

return ISort